package openase.audiosearch.ranking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

import openase.audio.AudioInfo;
import openase.audiosearch.FingerprintMatch;


public class LongestIncreasingSequenceOfMatchesRankingStrategy implements RankingStrategy {

	private static final Comparator<FingerprintMatch> QUERY_SMALLER_OR_REPOSITORY_IF_EQUALS = new Comparator<FingerprintMatch>() {

		@Override
		public int compare(FingerprintMatch o1, FingerprintMatch o2) {
			int delta = o1.getQueryFingerprint().getOffset() - o2.getQueryFingerprint().getOffset();
			if (delta == 0) {
				delta = o1.getRepositoryFingerprint().getOffset() - o2.getRepositoryFingerprint().getOffset();
			}
			return delta;
		}
	};

	@Override
	public AudioRanking rank(FingerprintMatch[] matchingFps) {
		Map<AudioInfo, List<FingerprintMatch>> map = new HashMap<AudioInfo, List<FingerprintMatch>>();

		for (FingerprintMatch match : matchingFps) {
			add(map, match.getRepositoryFingerprint().getSource(), match);
		}

		final AudioRankingBuilder builder = new AudioRankingBuilder();

		for (Entry<AudioInfo, List<FingerprintMatch>> entry : map.entrySet()) {
			AudioInfo audio = entry.getKey();
			FingerprintMatch[] matches = entry.getValue().toArray(new FingerprintMatch[0]);

			int bestSequence = findLongestIncreasingSequence(matches);

			builder.add(audio, bestSequence);
		}

		return builder.getAudioRanking();
	}

	private int findLongestIncreasingSequence(FingerprintMatch[] matches) {
		int matchesLen = matches.length;

		/*
		 * first sort by smallest query offset (or repository offset, if query offset equals) so that matches[i] is 'smaller' than matches[i+1] (in
		 * this case 'smaller' means that it has a smaller query offset, or that the query offsets are equal, but it is smaller in the repository
		 * offset).
		 * 
		 * This makes the search faster, because with the entries ordered we solve it in O(n^2)
		 */
		Arrays.sort(matches, QUERY_SMALLER_OR_REPOSITORY_IF_EQUALS);

		int best = 1;
		int[] DP = new int[matchesLen];

		DP[0] = 1;
		for (int i = 1; i < matchesLen; i++) {
			DP[i] = 1;

			for (int aPrev = 0; aPrev < i; aPrev++) {
				// if it makes a sequence...(this also implicitly checks uniqueness of both query fingerprint and repository fingerprint in the
				// sequence)
				if (queryAndRepositoryOffsetSmaller(matches[aPrev], matches[i])) {
					// checks if it is the best sequence
					if (DP[aPrev] + 1 > DP[i]) {
						// get this as the new best sequence from 0 to i
						DP[i] = DP[aPrev] + 1;
					}
				}
			}
			// if DP[i] is a longest sequence than 'best', update 'best'
			if (DP[i] > best) {
				best = DP[i];
			}
		}

		return best;
	}

	private static boolean queryAndRepositoryOffsetSmaller(FingerprintMatch a, FingerprintMatch test) {
		return a.getQueryFingerprint().getOffset() < test.getQueryFingerprint().getOffset() && a.getRepositoryFingerprint().getOffset() < test.getRepositoryFingerprint().getOffset();
	}

	private static void add(Map<AudioInfo, List<FingerprintMatch>> map, AudioInfo source, FingerprintMatch match) {
		List<FingerprintMatch> list = map.get(source);
		if (list == null) {
			list = new ArrayList<FingerprintMatch>();
			map.put(source, list);
		}
		list.add(match);
	}

}
